import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;
/**
 * Description:
 *      输入：nums1 = [2,4], nums2 = [1,2,3,4].
 *      输出：[3,-1]
 *      解释：nums1 中每个值的下一个更大元素如下所述：
 *      - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
 *      - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
 */
public class Test {
    public static int[] nextGreaterElement(int[] nums1, int[] nums2) {
        /*
        // 方法一 :
        int m = nums1.length, n = nums2.length;
        int[] elem = new int[m]; //存放返回结果的数组

        for(int i = 0; i < m; ++i) {
            int j = 0;
            while(j < n && nums2[j] != nums1[i]) { // nums2 数组中找到nums1中的数据
                ++j;
            }
            int k = j + 1; // 保存两个数组中相同数据的右边一个数据的下标
            while(k < n && nums2[k] < nums2[j]) { // 找下一个更大的元素
                ++k;
            }
            elem[i] = k < n ? nums2[k] : -1;
        }
        return elem;
        */


        //方法二: 单调栈 + 哈希表
        Map<Integer,Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        int[] elem = new int[nums1.length];

        for(int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while(!stack.isEmpty() && num > stack.peek()) {
                stack.pop();
            }
            map.put(num,stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }

        for(int i = 0; i < nums1.length; ++i) {
            elem[i] = map.get(nums1[i]);
        }

        return elem;
    }

    public static void main(String[] args) {
        int[] elem1 = {4,1,2};
        int[] elem2 = {1,3,4,2};

        System.out.println(Arrays.toString(nextGreaterElement(elem1, elem2)));
    }

}
